package _06_动态规划;

import java.util.Arrays;

public class _673_最长递增子序列的个数 {

    public static void main(String[] args) {
        _673_最长递增子序列的个数 v = new _673_最长递增子序列的个数();
        int[] nums = {3, 1, 2};
        System.out.println(v.findNumberOfLIS(nums));

    }

    public int findNumberOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int[] count = new int[nums.length];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int maxLen = 1;
        int maxCount = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    int value = dp[j] + 1;
                    if (value > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (value == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxCount = count[i];
            } else if (dp[i] == maxLen) {
                maxCount += count[i];
            }
        }
        return maxCount;
    }

}
